package trees;

public class ConvertArrayToBinaryTree {

	static class Node {
		Node left, right;
		int value;

		public Node(int value) {
			this.value = value;
		}
	}

	/**
	 * A tree is represented in a matrix form such that A[i,j] = 1 if j is the
	 * ancestor of i. Otherwise A[i,j] = 0. Given this construct a normal binary
	 * search tree.
	 */
	public static void main(String[] args) {

		int[][] array = new int[6][6];

		array[0][1] = 1;
		array[1][3] = 1;
		array[2][1] = 1;
		array[4][5] = 1;
		array[5][3] = 1;

		Node root = convertArrayToBST(array);

		print(root);
	}

	private static void print(Node root) {
		
		if (root != null) {
			if (root.left != null) {
				print(root.left);
			}
			System.out.print(root.value + " ");
			if (root.right != null) {
				print(root.right);
			}
		}
	}

	private static Node convertArrayToBST(int[][] array) {

		int i = findRoot(array);
		if (i != -1) {
			return createBST(i, array);
		}
		return null;
	}

	private static Node createBST(int i, int[][] array) {
		if (i != -1) {
			Node n = new Node(i);
			int[] ids = getChildNodeValues(i, array);
			n.left = createBST(ids[0], array);
			n.right = createBST(ids[1], array);
			return n;
		}
		return null;
	}

	private static int[] getChildNodeValues(int i, int[][] array) {

		int[] result = new int[2];
		result[0] = -1;
		result[1] = -1;

		for (int j = 0; j < array[i].length; j++) {
			if (array[j][i] == 1) {
				if (j > i) {
					result[1] = j;
				} else {
					result[0] = j;
				}
			}
		}

		return result;
	}

	private static int findRoot(int[][] array) {
		int root = -1;
		for (int j = 0; j < array[0].length; j++) {
			int isParent = 1;
			for (int i = 0; i < array.length; i++) {
				if (array[i][j] != 0) {
					isParent = -1;
					break;
				}
			}
			if (isParent == 1) {
				root = j;
				break;
			}
		}
		return root;
	}
}
